This relates generally to graphics processing to enable images to be generated on a computer display.
As part of graphics processing, it is necessary to determine whether a ray intersects triangles representing a scene. To actually test a ray against every single triangle in a scene made of up triangles, would take too long. This is especially so when the ray only intersects a few triangles in the scene. Thus, it is advantageous to hone in on the triangles that really need to be considered and avoid unnecessarily testing the ray against lots of triangles. A bounding volume hierarchy can be used to more quickly identify which triangles in a scene could be intersected by a ray.
Using a scene graph for a bounding volume hierarchy, one can divide the scene iterably into successively smaller sets of triangles. If the highest level set of triangles is not intersected by the ray then none of the smaller sets of triangles would be intersected by the ray. Thus in one case, the bounding volume hierarchy defining a scene may be divided in two so that one of the two portions contains approximately half of the triangles of the scene and the other portion contains the remainder of the triangles. Then the ray may be tested against each divided portion of the scene to determine whether the partial set of triangles would be intersected by the ray.
A scene graph includes a root node that holds the whole scene of triangles. Two child nodes split from the root mode may each be responsible for half the triangles of the scene, each triangle now holding a portion of the overall set of triangles.
Then, at each successive level, each node is responsible for fewer triangles. Information held in the node is the bounding volume of the region in space that its triangles reside within. Each time the set of triangles is split into at least two child nodes, the volume of the bounding volume hierarchy is reduced. By repeatedly shrinking the bounding volume in this way until it only contains a few triangles, you only test more extensively for ray intersection as needed. For example, if you test the ray against the root node bounding volume and it misses, it will miss every triangle in the scene.
If a ray hits a root node then you check against the two child nodes. Ideally the ray hits only one of the two child nodes which means, for the child that is missed, you can ignore all the triangles that it owns. Then you test the ray against two grandchildren of the child node that the ray hits and so on. Binary subdivision continues down to a so-called leaf node containing only a few triangles to test the ray against. If the ray hits both child nodes, then one is pushed onto a node stack for later traversal and traversal continued through the other child.
In some cases, each node may have more than two child nodes. Moreover, the hierarchical trees are rarely balanced because more triangles usually exist in one part of the scene than another.